package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/10/18 16:25
 **/
public class Day46_1_Num902_AtMostNGivenDigitSet {
    class Solution {
        public int atMostNGivenDigitSet(String[] digits, int n) {
            String s = Integer.toString(n);
            int m = digits.length, k = s.length();
            int[][] dp = new int[k + 1][2];
            dp[0][1] = 1;
            for (int i = 1; i <= k; i++) {
                for (int j = 0; j < m; j++) {
                    if (digits[j].charAt(0) == s.charAt(i - 1)) {
                        dp[i][1] = dp[i - 1][1];
                    } else if (digits[j].charAt(0) < s.charAt(i - 1)) {
                        dp[i][0] += dp[i - 1][1];
                    } else {
                        break;
                    }
                }

                if (i > 1) {
                    dp[i][0] += m + dp[i - 1][0] * m;
                }
            }
            return dp[k][0] + dp[k][1];
        }
    }
}